#include<cstdio>
#include<string.h>
#include<string>
#include<iostream>
#include<fstream>
#include<vector>
#include<cstdlib>
#include<set>
#include<map>
#include<stack>
#include<utility>
#include<climits>
#include"LinkedList.h"
#include"MultiKey.h"
using namespace std;
#include <boost/random/uniform_01.hpp>



class Graph{
public:
	int nNode; int nEdge;
	vector<short>degree; vector<bool> isDeleted;
	vector<LinkedList> LL;

	Graph(){
		nNode = 0; nEdge=0;
		LL=vector<LinkedList>();
		degree = vector<short>();
		isDeleted = vector<bool>();
	}
	~Graph(){
		//cout<<"Destroyer called"<<endl;
	}

	Graph(const int N){
		nNode = N; nEdge=0;
		LL=vector<LinkedList>();
		for(int i=0;i<nNode;i++) LL.push_back(LinkedList());


		for(int i=0;i<nNode;i++) {degree.push_back(0); isDeleted.push_back(false);}

	}
	Graph (const Graph &G){
		this->nNode = G.nNode; this->degree = G.degree; this->isDeleted = G.isDeleted;
		this->nEdge = G.nEdge;
		this->LL.clear();
		for(int i=0;i<this->nNode;i++) {
			LinkedList L = LinkedList();
			element *temp = G.LL[i].L; vector<int> T = vector<int>();
			while(temp!=NULL) {T.push_back(temp->nodeID); temp=temp->next;}

			for(unsigned j=0;j<T.size();j++) L.insert(T[j]);
			this->LL.push_back(L);
		}

	}

	void inline insert(const int source, const int dest){
		LL[source].insert(dest); //conn.insert(multiIntKey(source,dest));
		degree[source]+=1; nEdge+=1;
	}
	int inline find(const int source, const int dest){
		return LL[source].find(dest);

	}
	bool inline isConnected(const int source, const int dest){
		if(LL[source].find(dest)!=-1) return true;
		else return false;
	}

	int inline remove(const int source, const int dest){
		int rc=LL[source].remove(dest);
		//conn.erase(multiIntKey(source,dest));
		if(rc!=-1) {degree[source]-=1; nEdge-=1;}
		return rc;
	}
	void inline clear(const int x){
		if(x<LL.size()){
			vector<int> temp = LL[x].getElements();
			//for(unsigned i=0;i<temp.size();i++) conn.erase(multiIntKey(x,temp[i]));
			LL[x]=LinkedList(); degree[x]=0; isDeleted[x]=true;
			nEdge-=temp.size();
		}
		else{	cout<<"ERROR in Graph clear():, Node "<<x<<" does not exist"<<endl;}

	}
	void clear(){
		LL.clear(); nEdge=0;
	}
	void show(const int x){
		if(x<LL.size()){
			cout<<x<<" => "; LL[x].show();
		}else{
			cout<<"ERROR in Graph show(int):, Node "<<x<<" does not exist"<<endl;
		}

	}
	void show(){
		cout<<"**********Showing Graph Elements********"<<endl;
		for(unsigned i=0;i<LL.size();i++){
			cout<<i<<" => "; LL[i].show(); cout<<" Degree: "<<degree[i]<<endl;
		}cout<<endl;
	}
	vector<int> getAdjacencyList(const int xNode){
		vector<int> temp;
		if(xNode<LL.size()) temp = LL[xNode].getElements();
		else temp = vector<int>();
		return temp;
	}
	int inline getDegree(const int xNode){
		if(xNode<LL.size()) return LL[xNode].getNumberOfElements();
		else return 0;
	}
	void computeDegree(){
		nEdge=0;
		for(int i=0;i<nNode;i++) {degree[i]=LL[i].getNumberOfElements(); nEdge+=degree[i];}

	}
	void evidence(int xNode){
		if(xNode<nNode){
			vector<int> neighbours = LL[xNode].getElements();
			for(unsigned i=0;i<neighbours.size();i++){
						//Remove Edge towards the eliminated node
				this->remove(neighbours[i],xNode);
			}
			this->clear(xNode);
			degree[xNode]=SHRT_MAX;
			nNode-=1;
		}

	}
	void inline eliminate(int xNode){
		if(xNode<nNode){
			vector<int> neighbours = LL[xNode].getElements();
			set<multiIntKey> ngbrconn;
			for(unsigned i=0;i<neighbours.size();i++){
				vector<int> ngbradjlist = LL[neighbours[i]].getElements();
				for(unsigned j=0;j<ngbradjlist.size();j++){
					ngbrconn.insert(multiIntKey(neighbours[i],ngbradjlist[j]));
				}
			}
			for(unsigned i=0;i<neighbours.size();i++){
				//Remove Edge towards the eliminated node
				this->remove(neighbours[i],xNode);
				//Add nodes to the neighbours of the eliminated node
				for(unsigned j=0;j<neighbours.size() ;j++){

						//cout<<neighbours[i]<<" "<<neighbours[j]<<endl;
					if(ngbrconn.find(multiIntKey(neighbours[i],neighbours[j]))==ngbrconn.end() &&j!=i) insert(neighbours[i],neighbours[j]);

				}
			}
			this->clear(xNode);
			degree[xNode]=SHRT_MAX; isDeleted[xNode]=true;
		}

	}
	void getEliminationOrder(vector<int> &elimorder, vector<int> &fillinedge, int &maxWidth){
		computeDegree();
		int *fillin = (int*)malloc(nNode*sizeof(int));
		elimorder.clear();
		vector<pair<int,int> > temp= vector<pair<int,int> >();
		for(int i=0;i<nNode;i++){
			fillin[i]=0; set<multiIntKey> ngbrconn;
			vector<int> neighbours = LL[i].getElements();
			for(unsigned ii=0;ii<neighbours.size();ii++){
				vector<int> ngbradjlist = LL[neighbours[ii]].getElements();
				for(unsigned jj=0;jj<ngbradjlist.size();jj++){
					ngbrconn.insert(multiIntKey(neighbours[ii],ngbradjlist[jj]));
				}
			}
			for(unsigned ii=0;ii<neighbours.size();ii++){
				for(unsigned jj=ii+1;jj<neighbours.size();jj++){
					if(ngbrconn.find(multiIntKey(neighbours[ii],neighbours[jj]))==ngbrconn.end()) {
						fillin[i]+=1;
					}

				}

			}
			ngbrconn.clear();
			cout<<i<<" Degree: "<<degree[i]<<" Fill in edge: "<<fillin[i]<<endl;
			temp.push_back(pair<int,int>(fillin[i],i));
		}
		sort(temp.begin(),temp.end());

		for(unsigned i=0;i<temp.size();i++) { elimorder.push_back(temp[i].second); fillinedge.push_back(fillin[temp[i].second]); }
		free(fillin);


	}
	void Gibbs(){


	}
//	void getFinalMarginal(vector<int> &elimorder, const vector<int> fillin, int &maxWidth){
//
//		int count =0;
//		int *newfillin = (int*)malloc(nNode*sizeof(int));
//		while(count<nNode){
//			short min = SHRT_MAX; int minFillinNode = nNode;
//			for(int i=0;i<nNode;i++){
//				if(!isDeleted[i]){
//					if(min>fillin[i]) {min = fillin[i]; minFillinNode = elimorder[i];}
//				}
//			}
//			if(min + degree[minFillinNode]>maxWidth) maxWidth = min + degree[minFillinNode];
//			newfillin[count]=minFillinNode;
//
//			vector<int> neighbours = LL[minFillinNode].getElements();
//			multimap<int,int> ngbrconn;
//			for(unsigned i=0;i<neighbours.size();i++){
//				for(unsigned j=0;j<neighbours.size();j++){
//					ngbrconn.insert(pair<int,int>(neighbours[i],neighbours[j]));
//				}
//			}
//		    std::pair <std::multimap<int,int>::iterator, std::multimap<int,int>::iterator> ret;
//
//			for(unsigned i=0;i<neighbours.size();i++){
//				int conn=0;
//			    for (std::multimap<int,int>::iterator it=ret.first; it!=ret.second; ++it) conn++;
//			    fillin[neighbours[i]]-=(degree[neighbours[i]]-conn);
//			}
//			eliminate(minFillNode);
//			count++;
//			if(count%1000==0) cout<<"Node Eliminated: "<<minFillinNode<<",Induced Width:"<<maxWidth<<", Current No. of Edge:"<<nEdge/2<<endl;
//
//		}
//		elimorder = vector<int>(newfillin, newfillin+nNode);
//
//
//
//
//
//	}
};
